<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /* 
      https://leetcode-cn.com/problems/maximal-square/
      思路：https://leetcode-cn.com/problems/maximal-square/solution/jser-by-hyj8/
    */
    let matrix = [
      ["1", "0", "1", "0", "0"],
      ["1", "0", "1", "1", "1"],
      ["1", "1", "1", "1", "1"],
      ["1", "0", "0", "1", "0"],
    ];

    function maximalSquare(matrix) {
      let max = 0;
      let dp = new Array(matrix.length);

      for (let i = 0; i < matrix.length; i++) {
        dp[i] = new Array(matrix[i].length).fill(0);
        for (let j = 0; j < matrix[i].length; j++) {
          if (matrix[i][j] === '1') {
            if (i === 0 || j === 0)
              dp[i][j] = 1;
            else 
              dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
          }
          max = Math.max(max, dp[i][j]);
        }
      }
      return max * max;
    }
    console.log(maximalSquare(matrix));
  </script>
</body>

</html>